package codeRandomThoughts.Test113路径总和II;

import codeRandomThoughts.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;


//路径总和II二刷
public class Solution3 {
    int pathSum;
    List<Integer> path;
    List<List<Integer>> result;

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        pathSum = 0;
        path = new ArrayList<>();
        result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        path.add(root.val);
        pathSum += root.val;
        backTracking(root, targetSum);
        return result;
    }

    private void backTracking(TreeNode root, int targetSum) {
        //没看清楚终止条件,这里要到叶子节点
        if (root.left == null && root.right == null && pathSum == targetSum) {
            result.add(new ArrayList<>(path));
            return;
        }

        //单层逻辑
        if (root.left != null) {
            path.add(root.left.val);
            pathSum += root.left.val;
            backTracking(root.left, targetSum);
            pathSum -= root.left.val;
            path.remove(path.size() - 1);
        }

        if (root.right != null) {
            path.add(root.right.val);
            pathSum += root.right.val;
            backTracking(root.right, targetSum);
            pathSum -= root.right.val;
            path.remove(path.size() - 1);
        }
    }
}
